package com.gitee.wsl.struct.tree.sample.segment

//链接：https://juejin.cn/post/7287908385990770747

class SegmentTree3 {
    class Node {
        // left 和 right 不再表示区间范围而是表示左右子节点在 tree 中的索引位置
        var left: Int = 0
        var right: Int = 0

        var `val`: Int = 0

        var add: Int = 0
    }

    // 记录当前节点数
    var count: Int = 1

    var tree: Array<Node?> = arrayOfNulls(5e6.toInt())

    init {
        tree[count] = Node()
    }

    fun query(pos: Int, left: Int, right: Int, l: Int, r: Int): Int {
        if (l <= left && right <= r) {
            return tree[pos]!!.`val`
        }

        lazyCreate(pos)

        pushDown(pos, right - left + 1)

        var res = 0
        val mid = left + right shr 1
        if (l <= mid) {
            res += query(tree[pos]!!.left, left, mid, l, r)
        }
        if (r > mid) {
            res += query(tree[pos]!!.right, mid + 1, right, l, r)
        }

        return res
    }

    /**
     * 修改区间的值
     *
     * @param pos   当前节点的索引值
     * @param left  当前线段树节点表示的范围下界
     * @param right 当前线段树节点表示的范围上界
     * @param l     要修改的区间下界
     * @param r     要修改的区间上界
     * @param val   区间值变化的大小
     */
    fun update(pos: Int, left: Int, right: Int, l: Int, r: Int, `val`: Int) {
        // 当前区间被要修改的区间全部包含
        if (l <= left && right <= r) {
            tree[pos]!!.`val` += (right - left + 1) * `val`
            tree[pos]!!.add += `val`
            return
        }

        lazyCreate(pos)

        pushDown(pos, right - left + 1)

        val mid = left + right shr 1
        if (l <= mid) {
            update(tree[pos]!!.left, left, mid, l, r, `val`)
        }
        if (r > mid) {
            update(tree[pos]!!.right, mid + 1, right, l, r, `val`)
        }

        pushUp(pos)
    }

    // 为该位置创建节点
    private fun lazyCreate(pos: Int) {
        if (tree[pos] == null) {
            tree[pos] = Node()
        }
        // 创建左子树节点
        if (tree[pos]!!.left == 0) {
            tree[pos]!!.left = ++count
            tree[tree[pos]!!.left] = Node()
        }
        // 创建右子树节点
        if (tree[pos]!!.right == 0) {
            tree[pos]!!.right = ++count
            tree[tree[pos]!!.right] = Node()
        }
    }

    private fun pushDown(pos: Int, len: Int) {
        if (tree[pos]!!.left != 0 && tree[pos]!!.right != 0 && tree[pos]!!.add != 0) {
            // 计算左右子树的值
            tree[tree[pos]!!.left]!!.`val` += (len - len / 2) * tree[pos]!!.add
            tree[tree[pos]!!.right]!!.`val` += len / 2 * tree[pos]!!.add

            // 子节点懒惰标记
            tree[tree[pos]!!.left]!!.add += tree[pos]!!.add
            tree[tree[pos]!!.right]!!.add += tree[pos]!!.add

            tree[pos]!!.add = 0
        }
    }

    private fun pushUp(pos: Int) {
        tree[pos]!!.`val` = tree[tree[pos]!!.left]!!.`val` + tree[tree[pos]!!.right]!!.`val`
    }
}